package leetcode.problems.P206反转链表;

import java.util.List;

public class ReverseList {
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

// 一次遍历
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(-1, head), current = head, next = null;
        if (current == null) return null;
        next = current.next;
        while (next != null) {
            current.next = next.next;
            next.next = dummy.next;
            dummy.next = next;
            next = current.next;
        }
        return dummy.next;
    }
}

// 递归
class Solution2 {
    public ListNode reverseList(ListNode head) {
        return reverseList(head, null);
    }

    private ListNode reverseList(ListNode head, ListNode prev) {
        if (head == null) return prev;
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        return reverseList(next, prev);
    }
}